#include <bits/stdc++.h>
using namespace std;
const int N=1e3+50;
const int INF=0x3f3f3f3f;
int n;
struct HuffmanTree{
    char data;
    int weight;
    int parent, lson, rson;
};
struct CodeNode{
    int ch;
    char bits[N+1];
};
void SelectMin(HuffmanTree tree[], int len, int * pos1, int* pos2){
    int min=INF;
    int i, j;
    *pos1=0;
    *pos2=0;
    for(i=0; i<len; i++){
    if(tree[i].parent==-1)
        if(min>tree[i].weight){
            min=tree[i].weight;
            *pos1=i;
        }
    }
    min=INF;
    for(j=0; j<len; j++){
        if(j==*pos1)
            continue;
        if(tree[j].parent==-1){
            if(min>tree[j].weight){
                min=tree[j].weight;
                *pos2=j;
            }
        }
    }
}
void CreateHuffmanTree(HuffmanTree tree[], int n){
    int m=2*n;
    int i;
    for(i=n; i<m-1; i++){
        int pos1, pos2;
        HuffmanTree node;
        SelectMin(tree, i, &pos1, &pos2);
        //printf("pos1=%d,pos2=%d\n", pos1, pos2);
        node.weight=tree[pos1].weight+tree[pos2].weight;
        tree[pos1].parent=i;
        tree[pos2].parent=i;
        node.lson=pos1;
        node.rson=pos2;
        node.parent=-1;
        tree[i]=node;
    }
 }
void HuffmanEncoding(HuffmanTree tree[]){
    int c, p, i;
    int start;
    char cd[n+1];
    cd[n]='\0';
    for(i=0; i<n; i++){
        printf("\n");
        printf("%2d %c",tree[i].weight,tree[i].data);
        printf(":");
        start=n;
        c=i;
        while((p=tree[c].parent)!=-1)
        {
          if(tree[p].lson==c)
          {
            cd[--start]='0';
          }
          else
          {
            cd[--start]='1';
          }
          c=p;
        }
        printf(&cd[start]);
    }
 }

int main(void){
    HuffmanTree tree[N*2];
    printf("请输入字符数量\n");
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        tree[i].data='\0';
        tree[i].lson=-1;
        tree[i].rson=-1;
	    tree[i].parent=-1;
    }
    printf("请输入字符和对应的权值: \n");
    //a b c d e f g h 
    //5 29 7 8 14 23 3 11
    for(int i=0; i<n; i++){
        int weight;
        char ch[3];
        scanf("%s%d",ch,&weight);
        tree[i].data=ch[0];
        tree[i].weight=weight;
    }
    CreateHuffmanTree(tree, n);
    for(int i=0; i<2*n-1; i++){
        printf("tree[%d]:weight=%d \n",i, tree[i].weight);
    }
    HuffmanEncoding(tree);
    printf("\n");
    return 0;
 }